Speed

Bubble Sort

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended order. It is called bubble sort because the movement of array elements is just like the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly, the array elements in bubble sort move to the end in each iteration.Although it is simple to use, it is primarily used as an educational tool because the performance of bubble sort is poor in the real world. It is not suitable for large data sets. The average and worst-case complexity of Bubble sort is O(n²), where n is a number of items.

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. 1)Starting from the first index, compare the first and the second elements.
2. 2)If the first element is greater than the second element, they are swapped.
3. 3)Now, compare the second and the third elements. Swap them if they are not in order.
4. 4)The above process goes on until the last element.

2. Remaining Iteration

1. 1)The same process goes on for the remaining iterations.
2. 2)After each iteration, the largest element among the unsorted elements is placed at the end.

Merge Sort

Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm. Here, a problem is divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution.Time complexity of merge sort is O(nlogn)

Merge sort algorithm

The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1. After that, the merge function comes into play and combines the sorted arrays into larger arrays until the whole array is merged.

Merge function

Every recursive algorithm is dependent on a base case and the ability to combine the results from base cases. Merge sort is no different. The most important part of the merge sort algorithm is, you guessed it, merge step. The merge step is the solution to the simple problem of merging two sorted lists(arrays) to build one large sorted list(array). The algorithm maintains three pointers, one for each of the two arrays and one for maintaining the current index of the final sorted array.

Quick Sort

Quicksort is a sorting algorithm based on the divide and conquer approach where An array is divided into subarrays by selecting a pivot element (element selected from the array). While dividing the array, the pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot. The left and right subarrays are also divided using the same approach. This process continues until each subarray contains a single element. At this point, elements are already sorted. Finally, elements are combined to form a sorted array. Time complexity of quick sort id O(nlogn)

Working of Quicksort Algorithm

1. 1. Select the Pivot Element

   There are different variations of quicksort where the pivot element is selected from different positions. Here, we will be selecting the rightmost element of the array as the pivot element.

2. 2. Rearrange the Array

   Now the elements of the array are rearranged so that elements that are smaller than the pivot are put on the left and the elements greater than the pivot are put on the right.

3. Here is how we rearrange the array

   1)A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index
4. 2)If the element is greater than the pivot element, a second pointer is set for that element.
5. 3)Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.
6. 4)Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.
7. 5)The process goes on until the second last element is reached.
8. 6)Finally, the pivot element is swapped with the second pointer

9. 3. Divide Subarrays

   Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated.

Count Sort

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.Time complexity of count sort is O(n+k).

Working of Counting Sort

1. 1)Find out the maximum element (let it be max) from the given array.
2. 2)Initialize an array of length max+1 with all elements 0. This array is used for storing the count of the elements in the array.
3. 3)Store the count of each element at their respective index in count array For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position of count array. If element "5" is not present in the array, then 0 is stored in 5th position.
4. 4)Store cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array.
5. 5)Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated as shown in figure below.
6. 6)After placing each element at its correct position, decrease its count by one.

Insertion Sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. Insertion sort works similarly as we sort cards in our hand in a card game. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.Time complexity of insertion sort is O(n²)

Working of Insertion Sort

1. 1)The first element in the array is assumed to be sorted. Take the second element and store it separately in key. Compare key with the first element. If the first element is greater than key, then key is placed in front of the first element.
2. 2)Now, the first two elements are sorted. Take the third element and compare it with the elements on the left of it. Placed it just behind the element smaller than it. If there is no element smaller than it, then place it at the beginning of the array.
3. 3)Similarly, place every unsorted element at its correct position.